// 岛屿的最大面积： https://leetcode-cn.com/problems/max-area-of-island/

package main

import "math"

//  和 岛屿数量如出一辙~
func maxAreaOfIsland(grid [][]int) int {
	var dfs func(x, y int)
	dir := [][2]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}
	n, m := len(grid), len(grid[0])
	count := 0

	// 深度优先，找到一个块儿
	dfs = func(x, y int) {
		if grid[x][y] == 0 {
			return
		}
		// byte 类型数组，这里注意要用单引号
		grid[x][y] = 0
		count += 1

		for _, ac := range dir {
			newX := ac[0] + x
			newY := ac[1] + y
			// 剪枝
			if newX >= 0 && newY >= 0 &&
				newX < n && newY < m {
				dfs(newX, newY)
			}
		}
	}

	rst := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				// 调用深度优先遍遍历，找到这一块陆地
				dfs(i, j)
				rst = int(math.Max(float64(rst), float64(count)))
				count = 0
			}
		}
	}
	return rst
}


// 这种写法（Python版） 通过返回值。不使用全局变量
/*
class Solution:
	def dfs(self, grid, cur_i, cur_j) -> int:
		if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
			return 0
		grid[cur_i][cur_j] = 0
		ans = 1
		for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
			next_i, next_j = cur_i + di, cur_j + dj
			ans += self.dfs(grid, next_i, next_j)
		return ans

	def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
	ans = 0
	for i, l in enumerate(grid):
		for j, n in enumerate(l):
			ans = max(self.dfs(grid, i, j), ans)
	return ans
*/
